/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/unique-paths-ii
   @Language: C++
   @Datetime: 19-07-01 17:07
   */

class Solution {
public:
	unsigned int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		if(obstacleGrid.size()==0 || obstacleGrid[0].size()==0) return 0;
		int m=obstacleGrid.size(), n=obstacleGrid[0].size();
		vector<vector<unsigned int> > dp(m,vector<unsigned int>(n,0));
		if(obstacleGrid[0][0]==0) dp[0][0]=1;
		else return 0;
		for(int i=0; i<m; ++i){
			for(int j=0; j<n; ++j){
				if(obstacleGrid[i][j]) continue;
				if(i>0 && obstacleGrid[i-1][j]==0) dp[i][j]+=dp[i-1][j];
				if(j>0 && obstacleGrid[i][j-1]==0) dp[i][j]+=dp[i][j-1];
			}
		}
		return dp[m-1][n-1];
	}
};
